/*================================================================
*   文件名称：main.c
*   创 建 者：yang qiang
*   创建日期：2018年09月01日
*   描    述：
*   
================================================================*/


#include <iostream>
#include <vector>
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param inorder: A list of integers that inorder traversal of a tree
     * @param postorder: A list of integers that postorder traversal of a tree
     * @return: Root of a tree
     */
    TreeNode * buildTree(vector<int> &preorder, vector<int> &inorder) {
        // write your code here
        
        return build(0, preorder.size() -1, 0, inorder.size() - 1, preorder, inorder);
    }
    
    TreeNode *build(int pre_l, int pre_r, int in_l, int in_r, vector<int> &preorder, vector<int> &inorder){
        if( pre_r < pre_l || in_r < in_l )
            return NULL;

        int i = 0;
        TreeNode *root = new TreeNode(preorder[pre_l]);
        int target = preorder[pre_l];
        for(i; i <= in_r - in_l; i++){
            if( inorder[in_l + i] == target )
                break;
        }

        root->left = build(pre_l + 1, pre_l + i, in_l, in_l + i - 1, preorder, inorder);
        root->right = build(pre_l + i + 1, pre_r, in_l +i + 1, in_r, preorder,inorder);
        return root;
    }
};
